Search results for "CAT algorithms"

showing 1 items of 1 documents

On the exhaustive generation of k-convex polyominoes

2017

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.

General Computer SciencePolyomino0102 computer and information sciences02 engineering and technologyComputer Science::Computational Geometry01 natural sciencesConvexityTheoretical Computer ScienceCombinatoricsCAT algorithmIntegerExhaustive generation0202 electrical engineering electronic engineering information engineeringConvex polyominoeConvexity K-convex polyominoes.Convex polyominoesComputer Science::DatabasesMathematicsDiscrete mathematicsAmortized analysisMathematics::CombinatoricsDegree (graph theory)Settore INF/01 - InformaticaComputer Science (all)Regular polygonMonotone polygon010201 computation theory & mathematicsPath (graph theory)020201 artificial intelligence & image processingCAT algorithms; Convex polyominoes; Exhaustive generation;CAT algorithms
researchProduct